#ifndef DATA_STRUCTURE_AMGRAPH_H
#define DATA_STRUCTURE_AMGRAPH_H

#include "Graph.h"
#include<cmath>
#include <queue>
#include "algorithm"

class AMGraph : public Graph {
private:
    verType vexs[MVNum];
    ArcType matrix[MVNum][MVNum] = {MaxInt};//邻接矩阵
    vector<Edge *> edge;
protected:
    verType findNode(int i) override {
        return vexs[i];
    }

    void inputArc(verType v1, verType v2, ArcType w) override {
        int i = findVexIdx(v1);
        int j = findVexIdx(v2);
        edge.push_back(new Edge(i, j, w));
        matrix[i][j] = matrix[j][i] = w;
    }

public:
    AMGraph(int vexNum, int arcNum) : Graph(vexNum, arcNum) {
        for (auto &i : matrix) {//初始化
            for (int j = 0; j < MVNum; ++j) {
                i[j] = MaxInt;
            }
        }
        this->create();
    }

    void inputNode(int idx) {
        cin >> vexs[idx];//输入点信息
    }

    void inputArc() {
        verType v1, v2;
        ArcType w;
        cin >> v1 >> v2 >> w;
        inputArc(v1, v2, w);
    }

    void primCreateTree(verType startPoint) {
//        AMGraph *graph=new AMGraph(vexNum,vexNum-1);
        int sum = 0;
        int pointIdx = findVexIdx(startPoint);
        NearDge nearDge[MVNum];
        for (int i = 0; i < vexNum; ++i) {//第一个元素更新权值边数组
            if (i != pointIdx) {
                nearDge[i].adjvexIdx = pointIdx;
                nearDge[i].w = matrix[pointIdx][i];
            }
        }
        nearDge[pointIdx].w = 0;
        for (int i = 1; i < vexNum; ++i) {
            NearDge minW = {0, MaxInt};
            for (int j = 0; j < vexNum; ++j) {//找最小权值的边
                if (minW.w > nearDge[j].w && nearDge[j].w != 0) {
                    minW.adjvexIdx = j;
                    minW.w = nearDge[j].w;
                }
            }
            pointIdx = minW.adjvexIdx;
            sum += minW.w;
            nearDge[pointIdx].w = 0;
            verType fromPoint = vexs[nearDge[pointIdx].adjvexIdx];
            verType toPoint = vexs[pointIdx];
            cout << fromPoint << "——" << toPoint << endl;
            for (int j = 0; j < vexNum; ++j) {//更新权值边数组
                if (matrix[pointIdx][j] < nearDge[j].w) {
                    nearDge[j].adjvexIdx = pointIdx;
                    nearDge[j].w = matrix[pointIdx][j];
                }
            }
        }
        cout << "权值和:" << sum << endl;
    }

    static bool cmpEdge(Edge *edge1, Edge *edge2) {
        return edge1->w < edge2->w;
    }

    void kruskalCreateTree() {
        int sum = 0;
        int vexSet[vexNum];//标识每个点的联通分量
        sort(edge.begin(), edge.end(), cmpEdge);//排序
        for (int i = 0; i < vexNum; ++i) {//初始化每个点的连通分量设置为自身
            vexSet[i] = i;
        }
        for (int i = 0; i < arcNum; ++i) {
            int v1 = edge[i]->v1;
            int v2 = edge[i]->v2;
            int vs1 = vexSet[v1];
            int vs2 = vexSet[v2];
            if (vs1 != vs2) {
                cout << vexs[v1] << "——" << vexs[v2] << endl;
                sum += edge[i]->w;
                for (int j = 0; j < vexNum; ++j) {//合并联通分量
                    if (vexSet[j] == vs2) {
                        vexSet[j] = vs1;
                    }
                }
            }
        }
        cout << "权值和:" << sum << endl;
    }

};


AMGraph *createGraphTool() {
    int vexNum, arcNum;
    cout << "输入点数和边数:";
    cin >> vexNum >> arcNum;
    cout << "创建邻接矩阵图" << endl;
    return new AMGraph(vexNum, arcNum);
}

#endif //DATA_STRUCTURE_AMGRAPH_H
